﻿using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;
using System.Threading;

namespace Dwarf.Managed
{

    /// <summary>
    /// Solve the Graph traversal problem.
    /// </summary>
    /// <remarks> 
    ///For the demonstration purposes of the project,
    ///we have chosen Depth first search algorithm
    /// </remarks>
    class Solver
    {
        /// <summary>
        /// Instance of Graph.
        /// </summary>
        public Graph graph;

        public Solver()
        {
        }

        /// <summary>
        /// Based method.
        /// </summary>
        public void Solve()
        {
            // We use a concurrent stack (from System.Collections.Concurrent)
            // so we don't have to worry about multiple threads pushing
            // vertices on the stack at the same time.
            ConcurrentStack<int> s = new ConcurrentStack<int>();
            //set the head of graph
            int headId = graph.getHeadId();
            graph.Visit(headId);
            s.Push(headId);
            //while stack not empty 
            while (s.Count != 0)
            {
                //take the first element
                int u; 
                s.TryPeek(out u);
                //for all edges of current vertex
                bool hasNoVisited = true;
                int[] edges = graph.GetNeighbouringVertices(u);
                // NOTE: If edges aren't unique, then the following is not correct.
                //       In that case, GetVisited/Visit should be atomic.
                Parallel.For(0, edges.Length, (int j, ParallelLoopState loopState) =>
                {
                    int endVertex = edges[j];
                    bool visited = graph.GetVisited(endVertex) > 0;
                    if (!visited)
                    {
                        //adding new vertex to work stack
                        hasNoVisited = false;
                        s.Push(endVertex);
                        graph.Visit(endVertex);
                        loopState.Break();
                    }
                });
                if (hasNoVisited)
                {
                    s.TryPop(out u);
                }
            }
        }
    }
}